#include <stdio.h>
#include <stdlib.h>

/*
 * insert delete etc.
 */

/*

二叉树的性质：

    （1）、在二叉树的第i层上至多有2i-1个结点（i≥1）。

    （2）、深度为k的二叉树至多有2k-1个结点（k≥1）。

    （3）、对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。

    一棵深度为k且有2k-1个结点的二叉树称为满二叉树。

    可以对满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，自左至右，则由此可引出完全二叉树的定义。深度为k且有n个结点的二叉树，
	当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称之为完全二叉树。

	如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到最后一层，每层从左到右），则对任一结点i（1≤i≤n）,有

	（4）、具有n个结点的完全二叉树的深度为不大于log2n的最大整数加1。

    （5）、如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到最后一层，每层从左到右），则对任一结点i（1≤i≤n）,有

    a、如果i=1,则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点x（其中x是不大于i/2的最大整数）。

    b、如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。

    c、如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1。


二叉查找树

    二叉查找树（BinarySearch Tree，也叫二叉搜索树，或称二叉排序树Binary Sort Tree）或者是一棵空树，或者是具有下列性质的二叉树：

    （1）、若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值；

    （2）、若它的右子树不为空，则右子树上所有结点的值均大于它的根结点的值；

    （3）、它的左、右子树也分别为二叉查找树。


（1）、插入

    在二叉查找树中插入新结点，要保证插入新结点后仍能满足二叉查找树的性质。例子中的插入过程如下：

    a、若二叉查找树root为空，则使新结点为根；

    b、若二叉查找树root不为空，则通过search_bst_for_insert函数寻找插入点并返回它的地址（若新结点中的关键字已经存在，则返回空指针）；

    c、若新结点的关键字小于插入点的关键字，则将新结点插入到插入点的左子树中，大于则插入到插入点的右子树中。 


  （3）、删除

    删除某个结点后依然要保持二叉查找树的特性。例子中的删除过程如下：

    a、若删除点是叶子结点，则设置其双亲结点的指针为空。

    b、若删除点只有左子树，或只有右子树，则设置其双亲结点的指针指向左子树或右子树。

    c、若删除点的左右子树均不为空，则：

    1）、查询删除点的右子树的左子树是否为空，若为空，则把删除点的左子树设为删除点的右子树的左子树。(binary-operation-01.jpg)
	
	2）、若不为空，则继续查询左子树，直到找到最底层的左子树为止。binary-operation-02.jpg
*/

struct tree 
{
  int data;

  struct tree * lchild;
  struct tree * rchild;
};

struct tree * search_for_insert(struct tree ** root, int key)
{
  struct tree * src, * des;

  des = *root;
  while (des) {
    src = des;

    if (des->data == key)
      return NULL;

    des = (key < des->data) ? des->lchild : des->rchild;
  }

  return src;
}

void insert(struct tree ** root, int data)
{
  struct tree * src, * des;

  src = (struct tree *) malloc (sizeof(struct tree));
  if (!src) 
    perror("Allocate dynamic memory.\n");

  src->data = data;
  src->lchild = NULL;
  src->rchild = NULL;

  if (*root == NULL)
    *root = src;
  else {
    des = search_for_insert(root, data);
    if (des == NULL) {
      fprintf(stderr, "The %d already exists.\n", data);
      free(src);
      return ;
    }

    if (data < des->data)
      des->lchild = src;
    else
      des->rchild = src;
  }
}

int print(int data)
{
  printf(" %d ", data);
  return 1;
}

int preorder(struct tree * root, int (*visit) (int data))
{
  if (root) {
    if (visit(root->data))
      if (preorder(root->lchild, visit))
	if (preorder(root->rchild, visit))
	  return 1;
    return 0;
  }
  else
    return 1;
}

int inorder(struct tree * root, int (*visit) (int data))
{
  if (root) {
    if (inorder(root->lchild, visit))
      if (visit(root->data))
	if (inorder(root->rchild, visit))
	  return 1;

    return 0;
  }
  else
    return 1;
}

void delete(struct tree ** root, int data)
{
  struct tree * des, * parent, * src;

  des = *root;
  if (!des) {
    fprintf(stderr, "Not found %d.\n", data);
    return ;
  }

  if (des->data == data) {
    /* it's a leaf node */
    if (!des->rchild && !des->lchild) {
      *root = NULL;
      free(des);
    }
    /* the right child is NULL */
    else if (!des->rchild) {
      *root = des->lchild;
      free(des);
    }
    /* the left child is NULL */
    else if (!des->lchild) {
      *root = des->rchild;
      free(des);
    }
    /* the node has both children */
    else {
      src = des->rchild;
      
      /* the src without left child */
      if (!src->lchild)
	src->lchild = des->lchild;
      /* the src have left child */
      else {
	/* find the smallest node in the left subtree of src */
	while (src->lchild) {
	  /* record the parent node of src */
	  parent = src;
	  src = src->lchild;
	}
	
	parent->lchild = src->rchild;
	src->lchild = des->lchild;
	src->rchild = des->rchild;
      }

      *root = src;
      free(des);
    }
  }
  else if (data > des->data) 
    delete(&(des->rchild), data);
  else if (data < des->data)
    delete(&(des->lchild), data);
}

int main(int argc, char *argv[])
{
  int i, num;
  struct tree * root;

  root = NULL;
  if (argc < 2) {
    fprintf(stderr, "Usage : %s num\n", argv[0]);
    exit(-1);
  }

  num = atoi(argv[1]);
  int arr[num];
  printf("please enter %d integers:\n", num);
  
  for (i = 0; i < num; i++) {
    scanf("%d", &arr[i]);
    insert(&root, arr[i]);
  }

  printf("\npre order traverse: ");
  preorder(root, print);
  printf("\npost order traverse: ");
  inorder(root, print);
  printf("\n");

  delete(&root, 45);
  printf("\npre order traverse: ");
  preorder(root, print);
  printf("\npost order traverse: ");
  inorder(root, print);
  printf("\n");
}

/*

运行两次，以不同的顺序输入相同的六个关键字

[xiaozhi@linux tree]$./binary-operation 6
please enter 6 integers:
45 24 53 12 37 93

pre order traverse:  45  24  12  37  53  93 
post order traverse:  12  24  37  45  53  93 

pre order traverse:  53  24  12  37  93 
post order traverse:  12  24  37  53  93 


[xiaozhi@linux tree]$ ./binary-operation 6
please enter 6 integers:
12 24 37 45 53 93

pre order traverse:  12  24  37  45  53  93 
post order traverse:  12  24  37  45  53  93 

pre order traverse:  12  24  37  53  93 
post order traverse:  12  24  37  53  93 


根据前序遍历的结果可得到两次运行所产生的二叉查找树的形态并不相同，如下图：

		(a)						(b)

		  45					12
		  /\					 \
		/	\					  \
	  24	 53					  24	
	 /\	     /\					   \
	/  \    /  \					\
   12  37      93					37
									 \
									  \
									  45
									   \
									    \
										53
										 \
										  \
										  93


不同形态的地叉查找树
(a) 关键字序列为(45, 24, 53, 12, 37, 93)的二叉排序树.
(b) 关键字序列为(12, 24, 37, 45, 53, 93)的单支树.


*/



